package com.monday.greedy.algorithm;

import lombok.AllArgsConstructor;
import lombok.Builder;
import lombok.Data;
import lombok.NoArgsConstructor;

import java.util.Arrays;

/**
 *   假设我们有 1 元、2 元、5 元、10 元、20 元、50 元、100 元这些面额的纸币，
 *   它们的张数分别是 c1、c2、c5、c10、c20、c50、c100。
 *   我们现在要用这些钱来支付 K 元，最少要用多少张纸币呢？
 */
public class CoinChange {

    /**
     * 1、先对硬币进行排序
     * 2、从面值最大的硬币开始找零
     *   不一定是最优解
     */
    public void coinChange(Coin[] coins, int amount) {
        // 硬币面值从大到小排序
        Arrays.sort(coins, (a, b) -> b.value - a.value);
        System.out.println("排序后的硬币：" + Arrays.toString(coins));
        System.out.println("找零：" + amount + "元, ============================");

        int remaining = amount;
        for (Coin coin : coins) {
            int count = Math.min(remaining / coin.value, coin.count);
            remaining -= count * coin.value;
            System.out.println("面值为" + coin.value + "的硬币，找零" + count + "张，剩余" + remaining + "元");
        }

        if (remaining > 0) {
            System.err.println("===========无法找零");
        }
    }

    @Data
    @Builder
    @NoArgsConstructor
    @AllArgsConstructor
    public static class Coin {
        private int value;
        private int count;
        @Override
        public String toString() {
            return "(" + value + "," + count + ")";
        }
    }

}
